// 线段树1 区间修改 单信息
// https://soj.turingedu.cn/problem/60201/
int n;
int a[maxn];
ll sum[maxn << 2];
int tag[maxn << 2];

inline void merge(int now) { // merge the subtree
    sum[now] = sum[now << 1] + sum[now << 1 | 1];
}
inline void update_node(int now, int l, int r, ll x) { // update the node by tag
    sum[now] += x * (r - l + 1);
    tag[now] += x;
}
inline void push_down(int now, int l, int r) { // update the subnode and push down the tag
    if (tag[now] == 0) return;
    int mid = l + r >> 1;
    update_node(now << 1, l, mid, tag[now]);
    update_node(now << 1 | 1, mid + 1, r, tag[now]);
    tag[now] = 0;
}

void init(int now, int l, int r) { // init the tree
    if (l == r) {
        sum[now] = a[l];
        return;
    }
    int mid = l + r >> 1;
    init(now << 1, l, mid);
    init(now << 1 | 1, mid + 1, r);
    merge(now);
}

void update(int now, int l, int r, int s, int t, ll x) { // update the [s, t] by tag
    if (s <= l && r <= t) {
        update_node(now, l, r, x);
        return;
    }
    push_down(now, l, r);
    int mid = l + r >> 1;
    if (s <= mid) update(now << 1, l, mid, s, t, x);
    if (t > mid) update(now << 1 | 1, mid + 1, r, s, t, x);
    merge(now);
}

ll ask(int now, int l, int r, int s, int t) { // ask the [s, t]
    if (s <= l && r <= t) return sum[now];    // cover
    push_down(now, l, r);
    int mid = l + r >> 1;
    if (t <= mid) return ask(now << 1, l, mid, s, t);
    if (s > mid) return ask(now << 1 | 1, mid + 1, r, s, t);
    return ask(now << 1, l, mid, s, t) + ask(now << 1 | 1, mid + 1, r, s, t);
}
